package leetcode;

/**
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 *
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Leetcode003 {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m == 0) {
            return nums2[m / 2];
        }
        if (n == 0) {
            return nums1[n / 2];
        }
        int medianIndex;
        int rem = (m + n) % 2;
        if (m < n) {
            medianIndex = m + (n - m) / 2;
        }else {
            medianIndex = n + (m - n) / 2;
        }
        int index1 = 0;
        int index2 = 0;
        int pos = 1;
        while (index1 + index2 < medianIndex) {
            int a = nums1[index1];
            int b = nums2[index2];
            if (a < b) {
                if (index1 == m - 1) {
                    index2++;
                    pos = 2;
                }else {
                    index1++;
                    pos = 1;
                }
            }else {
                if (index2 == n - 1) {
                    index1++;
                    pos = 1;
                }else {
                    index2++;
                    pos = 2;
                }

            }
        }
        System.out.println(index1);
        System.out.println(index2);
        System.out.println(pos);
        if (rem == 1) {
            return pos == 1 ? nums1[--index1]: nums2[--index2];
        }else {
            return (pos == 1 ? nums1[--index1] + nums2[index2]: nums1[index1] + nums2[--index2]) / 2.0;
        }
    }
}
